package com.wsy.wsyojcodesandbox.utils;

import java.util.Arrays;
import java.util.List;

public class KmpUtil {
    private List<String> blackList = null;

    public KmpUtil(List<String> blackList) {
        this.blackList = blackList;
    }

    public boolean hasMatch(String code) {
        for(String s: blackList) {
            if(match(code, s))
                return true;
        }
        return false;
    }

    private boolean match(String code, String pattern) {
        char[] cs = code.toCharArray();
        char[] ps = pattern.toCharArray();
        int[] next = getNext(ps);
        int cIndex = 0, pIndex = 0;
        while(cIndex < cs.length && pIndex < ps.length) {
            if(cs[cIndex] == ps[pIndex]) {
                cIndex++;
                pIndex++;
            }else if(next[pIndex] == -1) {
                cIndex++;
            }else {
                pIndex = next[pIndex];
            }
        }
        return pIndex == ps.length;
    }

    private int[] getNext(char[] pattern) {
        if(pattern.length == 1)
            return new int[] {-1};
        if(pattern.length == 2)
            return new int[] {-1, 0};

        int N = pattern.length;
        int[] next = new int[N];
        next[0] = -1;
        next[1] = 0;
        for(int i = 2; i < N; i++) {
            int pre = next[i - 1];
            while(pre != -1 && pattern[pre] != pattern[i])
                pre = next[pre];
            next[i] = pre + 1;
        }
        return next;
    }

}
